#!/usr/bin/python2.6

import copy
import itertools
import operator
import random
import sys

def nullShuffler(cards):
	pass

CASH_OUT_DEPTH=6

def flatten(listOfLists):
    "Flatten one level of nesting"
    return itertools.chain.from_iterable(listOfLists)

def unique(seq): 
    # not order preserving 
    set = {} 
    map(set.__setitem__, seq, []) 
    return set.keys()

class Logger(object):
	def __init__(self):
		self._indentLevel = -1
		self._enabled = True

	def indent(self):
		self._indentLevel += 1

	def log(self, string):
		if self._enabled and self._indentLevel < 40:
			print '  '*self._indentLevel + `self._indentLevel` + ') ' + string

	def outdent(self):
		self._indentLevel -= 1

	def enableLogging(self, enabled):
		self._enabled = enabled
		

def xuniqueCombinationsWithCountAndDepth(items, n, depth=None):
	if depth <= 0:
		return xuniqueCombinationsWithCount(items, n, just_one=True)
	
	if depth > CASH_OUT_DEPTH:
		return xuniqueCombinationsWithCount(items, n, just_one=True)
		
	return xuniqueCombinationsWithCount(items, n, None)


def filterByDepth(srted, depth):
	groups = []
	uniquekeys = []
	for k, g in itertools.groupby(srted, lambda x: x[1]):
	    groups.append(list(g))      # Store group iterator as a list
	    uniquekeys.append(k)
	if depth is not None and len(groups) > depth:
		groups = groups[:depth]
		srted = list(flatten(groups))
		total = reduce(lambda x,y: x + y[1], srted, 0)
		srted = ((x[0], float(x[1])/float(total)) for x in srted)		
	return srted


def xuniqueCombinationsWithCount(items, n, just_one=False):
	counts = {}
	total = 0
	for combo in itertools.combinations(items, n):
		combo = tuple(combo)
		counts[combo] = counts.get(combo, 0) + 1
		total += 1
	srted = sorted(counts.iteritems(), key=lambda x: (x[1], x[0]), reverse=True)
	srted = [(x[0], float(x[1])/float(total)) for x in srted]
	
	if just_one:
		yield 1.0, srted[0][0]
		return
	srted = filterByDepth(srted, 1)
	for s in srted:
#		print 'yield ', float(s[1])/float(total), s[0]
		yield float(s[1]), s[0]


class Card(object):
	def __init__(self, name, cost, value, vps, starting_count):
		self._name = name
		self._cost = cost
		self._value = value
		self._vps = vps
		self._starting_count = starting_count
	def getCost(self):
		return self._cost
	def getValue(self):
		return self._value
	def getStartingCount(self):
		return self._starting_count
	def getVictoryPoints(self):
		return float(self._vps)
	def __repr__(self):
		return self._name
#               Name,       cost, coins, vps, starting count
estate =   Card('estate',   2, 0, 1, 8)
duchy =    Card('duchy',    5, 0, 3, 8)
province = Card('province', 8, 0, 6, 8)
copper =   Card('copper',   0, 1, 0, 60)
silver =   Card('silver',   3, 2, 0, 40)
gold =     Card('gold',     6, 3, 0, 30)
chapel =   Card('chapel',   2, 0, 0, 10)
curse =    Card('curse',    0, 0, -1,10)
supercurse = Card('supercurse',  0, 0, -1,10)

all_cards = [estate, duchy, province, copper, silver, gold, chapel]


class Hand(object):	
	def __init__(self, cards, probability=1.0):
		self._cards = cards
		self._probability = probability

	def __repr__(self):
		return 'Hand(%.4f, %s)' % (self._probability, self._cards)

	def canAfford(self, card_to_buy):
		return self.getCoins() >= card_to_buy.getCost()

	def getActions(self):
		actions = []
		if self._cards.count(chapel) <= 0:
			return actions

		cards_without_chapel = list(copy.copy(self._cards))
		cards_without_chapel.remove(chapel)
		cards_without_chapel.sort()
		combinations = []
		for i in range(len(cards_without_chapel)):
			combinations += itertools.combinations(cards_without_chapel, i+1)
		combinations = unique(combinations)
		if len(cards_without_chapel) > 0:
			actions = [ChapelAction(x) for x in combinations] + actions
		return actions

	def getBuys(self, game):
		actions = [buy_nothing_action]
		if game.getSupplyCount(chapel) > 0 and self.canAfford(chapel):
			actions = [buy_chapel_action] + actions
		
		for treasure in [copper, silver, gold]:
			if game.getSupplyCount(treasure) > 0 and self.canAfford(treasure):
				actions = [buy_treasure_action] + actions
				break
		for victory in [estate, duchy, province]:
			if game.getSupplyCount(victory) > 0 and self.canAfford(victory):
				actions = [buy_victory_action] + actions
				break

		return actions

	def getCards(self):
		return self._cards

	def getCoins(self):
		return reduce(lambda x, y: x + y.getValue(), self._cards, 0)

	def getMoves(self, game):
		return self.getActions() + self.getBuys(game)

	def getProbability(self):
		return self._probability

	def remove(self, cards_to_remove):
		my_cards = list(self._cards)
		for card in cards_to_remove:
			my_cards.remove(card)
		return Hand(my_cards, self._probability)


class NodeHistory(object):
	def __init__(self, payoff=0, test_game=None, hand=None, child_node_history=None):
		if child_node_history is None:
			child_nodes = []
		else:
			child_nodes = child_node_history._actions
		self._payoff = payoff
		if test_game is None:
			self._actions = []
			return
		self._actions = [(test_game.getAction(), 'hand: ' + str(hand), test_game.getExecuted()
		, str(test_game)
		)]+ child_nodes
#str(test_game), 
	def getDebugActions(self):
		return self._actions

	def getActions(self):
		return [x[0] for x in self._actions]

	def getPayoff(self):
		# Rounds so we don't get screwed by miniscule floating point differences.
		return round(self._payoff, 4)

	def setPayoff(self, payoff):
#		print 'set payoff: ' + `payoff`
		self._payoff = payoff


class Game(object):
	def __init__(self, shuffler=nullShuffler, supply=None, initial_deck=None,
		discards=None, phase='deal', turn_number=-1, logger=None):
		if discards is None:
			self._discards = []
		else:
			self._discards = discards
		self._shuffler = shuffler
		if supply is None:
			self._supply = self._buildSupply()
		else:
			self._supply = supply
		if initial_deck is None:
			self._deck =  [copper] * 7 + [estate] * 3
		else:
			self._deck = initial_deck
		self._turn_number = turn_number
		if logger is None:
			self._logger = Logger()
		else:
			self._logger = logger
		self._phase = phase
		shuffler(self._deck)
	
	def __repr__(self):
		return ("deck: " + `self._deck` + ", discards: " + `self._discards`)
	
	def _buildSupply(self):
		supply = {}
		for card in all_cards:
			supply[card] = card.getStartingCount()
		return supply

	def buy(self, hand, card):
		if not self.canBuy(hand, card):
			return self
		discards = copy.copy(self._discards) + [card]
		supply = copy.copy(self._supply)
		supply[card] -= 1

		return Game(shuffler=self._shuffler, supply=supply, 
			initial_deck=self._deck, discards=discards, phase='deal', logger=self._logger)

	def canBuy(self, hand, card):
		if not hand.canAfford(card):
			return False
		if not self._supply.has_key(card) or self._supply[card] <= 0:
			return False
		return True

	def chapel(self, hand, cards):
		discards = copy.copy(self._discards) + [chapel]
		
		chapelledGame = Game(shuffler=self._shuffler, supply=self._supply,
			initial_deck=self._deck, discards=discards, phase=self._phase,
			logger=self._logger)
		return chapelledGame, hand.remove(cards + (chapel,))
	
	def deal(self):
		deck = copy.copy(self._deck)
		discards = copy.copy(self._discards)
		if len(deck) < 5:
			deck += discards
			discards = []
			self._shuffler(deck)
		hand = deck[:5]
		deck = deck[5:]
		self._logger.log('deal:' + `(hand, discards, deck)`)
		dealtGame = Game(shuffler=self._shuffler, supply=self._supply,
			initial_deck=deck, discards=discards, phase=self._phase,
			turn_number=self._turn_number+1, logger=self._logger)
		return dealtGame, Hand(hand)

	def endTurn(self, hand):
		discards = copy.copy(self._discards) + list(hand.getCards())
		return (Game(shuffler=self._shuffler, supply=self._supply,
			initial_deck=self._deck, discards=discards, phase=self._phase,
			turn_number=self._turn_number, logger=self._logger),
			Hand([], hand.getProbability()))

	def gameOver(self):
		return self._supply[province] <= 0

	def getDeck(self):
		return self._deck

	def getDiscards(self):
		return self._discards

	def getPhase(self):
		return self._phase

	def getSupplyCount(self, card):
		return self._supply.get(card, 0)

	def getTurnNumber(self):
		return self._turn_number

	def getVictoryPoints(self, hand):
#		self._logger.log("all cards: " + `(self._discards, self._deck, list(hand.getCards()))`)
		vps = reduce(lambda x, y: x + y.getVictoryPoints(),
			self._discards + self._deck + list(hand.getCards()), 0)
		self._logger.log("game vp's: " + `self` + ', hand: ' + `hand` + " --> " +
			`vps`)
		return vps

	def multiDeal(self, depth):
		remaining = ()
		self._logger.log('started with ' + `self._deck` + ', ' + `self._discards`)
		deck = self._deck
		discards = self._discards
		if len(deck) < 5:
			remaining = tuple(deck)
			deck = discards
			discards = []

		for p, cards in xuniqueCombinationsWithCountAndDepth(sorted(deck),
			min(5 - len(remaining), len(deck)), depth):
			
			self._logger.log('multidealing: ' + `remaining` + ',' + `deck` +
				' --> p' + ('%.4f' % p) + `(remaining + cards)`)
			hand = Hand(remaining + cards, p)
			new_deck = copy.copy(deck)
			for card in cards:
				try:
					self._logger.log('removing ' + `card`)
					new_deck.remove(card)
				except ValueError:
					print "missing card"
					sys.exit(1)

			game = Game(shuffler=self._shuffler, supply=self._supply,
					initial_deck=new_deck, discards=discards, phase='buy',
					turn_number=self._turn_number + 1, logger=self._logger)
			
			yield game, hand

	def _startTurn(self, hand):
		flip = False
		deck = copy.copy(self._deck)
		discards = copy.copy(self._discards)
		for card in hand:
			try:
				deck.remove(card)
			except ValueError:
				discards.remove(card)
				flip = True

		if flip:
			if len(deck) > 0:
				print "deck should be empty on flip"
				sys.exit(1)
			deck = discards
			discards = []

		return Game(shuffler=self._shuffler, supply=self._supply,
				initial_deck=deck, discards=discards, phase='buy',
				turn_number=self._turn_number + 1, logger=self._logger)

class Action(object):
	def __init__(self, name):
		self._name = name

	def __repr__(self):
		return self._name

	def getName(self):
		return self._name


class BuyNothingAction(Action):
	def __init__(self):
		super(BuyNothingAction, self).__init__('buy_nothing')

	def act(self, game, hand):
		game, hand = game.endTurn(hand)		
		return self.getName(), game, hand


class BuyCategoryAction(Action):
	def _tryBuy(self, game, hand, cards):
		for card in cards:
			if game.canBuy(hand, card):
				game = game.buy(hand, card)
				return game, card

	def _act(self, game, hand, cards):
		game, card = self._tryBuy(game, hand, cards)
		executed = 'buy(%s)' % card
		game, hand = game.endTurn(hand)
		return executed, game, hand


class BuyVictoryAction(BuyCategoryAction):
	def __init__(self):
		super(BuyVictoryAction, self).__init__('buy:victory')

	def act(self, game, hand):
		return super(BuyVictoryAction, self)._act(game, hand, [province, duchy, estate])


class BuyTreasureAction(BuyCategoryAction):
	def __init__(self):
		super(BuyTreasureAction, self).__init__('buy:treasure')

	def act(self, game, hand):
		return super(BuyTreasureAction, self)._act(game, hand, [gold, silver, copper])


class BuyAction(Action):
	def __init__(self, card):
		super(BuyAction, self).__init__('buy:' + card)
		self._card = card

	def act(self, game, hand):
		game = game.buy(hand, self._card)
		game, hand = game.endTurn(hand)
		return 'buy(%s)' % card, game, hand


class ChapelAction(Action):
	def __init__(self, cards):
		super(ChapelAction, self).__init__('chapel')
		self._cards = cards

	def __repr__(self):
		return self._name + `self._cards`

	def act(self, game, hand):
		return ('chapel',) + game.chapel(hand, self._cards)

	def getCards(self):
		return self._cards

buy_nothing_action = BuyNothingAction()
buy_victory_action = BuyVictoryAction()
buy_treasure_action = BuyTreasureAction()
buy_chapel_action = BuyAction('chapel')


def play(game, strategy):
	while game.getSupplyCount(province) > 0:
		game, hand = game.deal()
		game = strategy.buyPhase(game, hand)
	return game, hand


class OptimizableGameBase(object):
	def getAction(self):
		return self._action

	def getChildNodes(self, current_depth):
		moves = self._hand.getMoves(self._game)
		if current_depth > CASH_OUT_DEPTH:
			best_payoff = -10000000000
			best_child = None
			for move in moves:
				child = self.execute(move)
				if child.getPayoff() > best_payoff:
					best_child = child
					best_payoff = child.getPayoff()
				self._logger.log('cash-out: ' + `best_payoff` + `move` + '/' + `moves`)			
			yield best_child
			return

		for move in moves:
			child = self.execute(move)
			self._logger.log(`move` + '/' + `moves`)			
			yield child

	def getExecuted(self):
		return self._bought

	def getHand(self):
		return self._hand


class OptimizableGame(OptimizableGameBase):
	def __init__(self, logger, game, hand=None, action=None, bought=None):
		if logger is None:
			self._logger = Logger()
		else:
			self._logger = logger		
		self._game = game
		self._bought = None
		if hand is None:
			self._hand = []
		else:
			self._hand = hand
		self._action = action
		self._bought = bought

	def __repr__(self):
		return str(self._hand) + ", " + str(self._game)

	def deal(self, depth=None):
		for game, deal in self._game.multiDeal(depth):
			dealt = OptimizableGame(self._logger, game=game, hand=deal)
			self._logger.log("hand: " + `deal` + ', ' + `self`)
			yield dealt

	def execute(self, action):
		bought, game, hand = action.act(self._game, self._hand)
		executed = OptimizableGame(self._logger, game, hand, action=action,
			bought=bought)
		self._logger.log(executed._bought + ", " + `executed` + ", hand: " +
			`executed._hand`)
		return executed

	def getHand(self):
		return self._hand

	def getPayoff(self):
		return self._game.getVictoryPoints(self._hand)

	def isDeal(self):
		return self._game.getPhase() == 'deal'

	def isGameOver(self):
		self._game.getSupplyCount(province) == 0


class Minimax(object):
	def __init__(self, max_depth=4, logger=None):
		if logger is None:
			self._logger = Logger()
		else:
			self._logger = logger
		self._trials = 0
		self._max_depth = max_depth
		self._action_log = []

	def _optimize_hand(self, game, current_depth):
		self._logger.indent()

		node_history = NodeHistory(-100000000)
		parent_payoff = game.getPayoff()
		child_nodes = game.getChildNodes(current_depth)
		for child_node in child_nodes:
#			if current_depth > 20 and child_node.getPayoff() <= parent_payoff:
#				self._logger.log('---------------SKIPPING---------------' + `child_node.getAction()`)
#				continue
			child_node_history = self.optimize(child_node, current_depth+1, True)
			if child_node_history.getPayoff() > node_history.getPayoff():
#				self._logger.log('--beat previous: ' +  `node_history.getPayoff()` + 
#					':' + `node_history.getDebugActions()`)
				node_history = NodeHistory(child_node_history.getPayoff(), child_node, 
					game.getHand(), child_node_history)

		self._logger.log('BEST: ' + `node_history.getPayoff()` + ':' + `node_history.getDebugActions()`)
		self._logger.outdent()
		return node_history

	def _optimize_deal(self, game, current_depth):
		self._logger.indent()
#		print "od: 1. opt", game

		most_probable_node_history = None
		total_payoff = 0.0
		for test_game in game.deal(current_depth):
#			print "od: 2a. opt", game
			node_history = self.optimize(test_game, current_depth+1, False)
			current_payoff = node_history.getPayoff() * test_game.getHand().getProbability()
			total_payoff += current_payoff
#			print "od: 2b. opt", game
			self._logger.log("payoff: %.4f*%.4f --> %.4f, total: %.4f" %
				(node_history.getPayoff(), test_game.getHand().getProbability(), current_payoff,
				total_payoff))
			if most_probable_node_history is None:
				most_probable_node_history = node_history

#		print "od: 3. opt", game
#		self._logger.log('total payoff: ' + `total_payoff`)
		most_probable_node_history.setPayoff(total_payoff)
		self._logger.outdent()
		return most_probable_node_history

	def getActionLog(self):
		print self._action_log

	def getTrials(self):
		return self._trials
	
	def optimize(self, game, current_depth=0, deal=True):
#		print "1. opt", game
		self._trials += 1

		if current_depth >= self._max_depth or game.isGameOver():
#			print "2. opt", game
			return NodeHistory(game.getPayoff())

		if game.isDeal():
#			print "3. opt", game
			return self._optimize_deal(game, current_depth)
		else:
#			print "4. opt", game
			return self._optimize_hand(game, current_depth)
		
#		print "5. opt", game

class BigMoneyStrategy(object):
	def buyPhase(self, game, hand):
		if (game.getSupplyCount(gold) < gold.getStartingCount() and
			hand.canAfford(province)):
			game = game.buy(hand, province)
			hand = game.endTurn(hand)
		elif (game.getSupplyCount(province) <= 5 and
			hand.canAfford(duchy)):
			game.buy(hand, duchy)
			game.endTurn(hand)
		elif (game.getSupplyCount(province) <= 2 and
			hand.canAfford(estate)):
			game.buy(hand, estate)
			game.endTurn(hand)
		elif hand.canAfford(gold):
			game.buy(hand, gold)
			game.endTurn(hand)
		elif hand.canAfford(silver):
			game.buy(hand, silver)
			game.endTurn(hand)
		print game.getTurnNumber(), game.getHand(), game.getDiscards()
		

class AlwaysBuyVictoriesStrategy(object):
	def play(self, game):
		while game.getSupplyCount(estate) > 0:
			game.deal()
			game.buy(estate)

			
class BuyCopperFirstStrategy(object):
	def play(self, game):
		game.deal()
		game.buy(copper)
#		print game.getTurnNumber(), game.hand, game.discards
		while game.getSupplyCount(estate) > 0:
			game.deal()
			game.buy(estate)
#			print game.getTurnNumber(), game.hand, game.discards


def randomShuffler(cards):
	random.shuffle(cards)

def testStrategy(strategy, count):
	totalTurns = 0
	turnsTaken = {}
	for trials in range(count):
		game = Game()
		game.play(strategy)
		turn_number = game.getTurnNumber()
		if not turnsTaken.has_key(turn_number):
			turnsTaken[turn_number] = 0
		turnsTaken[turn_number] += 1
		totalTurns += game.getTurnNumber()
	return turnsTaken
	print "always buy took ", turnsTaken

	
def main():
	print "BIG MONEY: ", testStrategy(BigMoneyStrategy(), 1)
#	print "always buy victories: ", testStrategy(AlwaysBuyVictoriesStrategy(), 1000)
#	print "copper first: ", testStrategy(BuyCopperFirstStrategy(), 1000)

if __name__ == '__main__':
	main()

